算法内容
本文件实现 LeetCode 2049「统计最高分的节点数目」。题目要求删除每个节点后，计算剩余各连通块大小的乘积，并统计最高分节点数量。
第一版使用 unordered_map<int, vector<int>> 建树，先通过 DFS 计算每个节点子树大小，再枚举节点计算分数：父侧连通块大小为 n - size[i]，每个子树连通块大小为对应子节点的 size。SolutionBetter 针对二叉树性质，用 vector<pair<int, int>> 保存左右孩子，避免 map 和动态 vector 带来的额外开销。整体时间复杂度 O(n)，空间复杂度 O(n)。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| #include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
#include<set>
using namespace std;
class Solution {
public:
template<class T>
void printVec(const vector<T> &v, const string& head = "") {
if(head != "") {
cout << head << ": ";
}
for (T i : v) {
cout << i << " ";
}
cout << "\n";
}
vector<int> size;
vector<int> parents;
unordered_map<int, vector<int>> children;
int n;
long long max = LONG_LONG_MIN;
int maxn = 0;
int countHighestScoreNodes(vector<int>& parents) {
int n = parents.size();
this->parents = parents;
this->size = vector<int>(n, 1);
this->n = n;
for(int i = 0; i < n; i++) {
getG(i);
}
getSize(0);
for(int i = 0; i < n; i++) {
calScore(i);
}
return maxn;
}
int getSize(int root) {
int childNum = children[root].size();
if(childNum == 0) {
size[root] = 1;
} else if(childNum == 1) {
size[root] += getSize(children[root][0]);
} else {
size[root] += getSize(children[root][0]) + getSize(children[root][1]);
}
return size[root];
}
void calScore(int i) {
int parent = parents[i];
long long res = (parent == -1) ? 1 : (size[0] - size[i]);
vector<int>& childi = children[i];
for(int child : childi) {
res *= size[child];
}
if(res > max) {
max = res;
maxn = 1;
} else if(res == max) {
maxn++;
}
}
void getG(int i) {
int parent = parents[i];
if(parent == -1) {
return;
} else {
children[parent].push_back(i);
}
}
};
int main() {
Solution s;
vector<int> v = {-1,2,0,2,0};
cout << s.countHighestScoreNodes(v) << endl;
return 0;
}
class SolutionBetter {
public:
vector<int> parents;
vector<pair<int, int>> children;
vector<int> size;
int n;
long long max = LONG_LONG_MIN;
int maxn = 0;
int countHighestScoreNodes(vector<int>& parents) {
int n = parents.size();
this->parents = parents;
this->children = vector<pair<int, int>>(n, {-1,-1});
this->size = vector<int>(n, 1);
this->n = n;
for(int i = 0; i < n; i++) {
int parent = parents[i];
if(parent == -1) {
continue;
} else {
if(children[parent].first == -1) {
children[parent].first = i;
} else {
children[parent].second = i;
}
}
}
getSize(0);
for(int i = 0; i < n; i++) {
int parent = parents[i];
long long res = (parent == -1) ? 1 : (size[0] - size[i]);
pair<int, int>& childi = children[i];
res *= childi.first != -1 ? size[childi.first] : 1;
res *= childi.second != -1 ? size[childi.second] : 1;
if(res > max) {
max = res;
maxn = 1;
} else if(res == max) {
maxn++;
}
}
return maxn;
}
int getSize(int root) {
pair<int, int> child = children[root];
int a = 0, b = 0;
if(child.first != -1) {
a = getSize(child.first);
}
if(child.second != -1) {
b = getSize(child.second);
}
size[root] = 1 + a + b;
return size[root];
}
};
|